/*
合并有序链表
1. 尾插法初始化链表
2. merge有序链表
*/
#include <iostream>
using namespace std;

struct Node
{
	int data;
	Node* next = NULL;
	Node(int value):data(value){};
	Node(){};
};

Node* MergeLinkList(Node* head1,Node* head2){	//判断是否有空链
	if(head1 == NULL || head1->next == NULL){
		return head2;
	}
	if(head2 == NULL || head2->next == NULL){
		return head1;
	}
	Node* p1 = head1->next;
	Node* p2 = head2->next;
	Node* new_head = new Node;
	Node* cur = new_head;
	while(p1 != NULL && p2 != NULL){
		if(p1->data <= p2->data){
			cur->next = p1;	
			p1 = p1->next;
		}
		else{
			cur->next = p2;
			p2 = p2->next;
		}
		cur = cur->next;		//更新当前结点位置
	}
	if(p1){
		cur->next = p1;
	}
	else{
		cur->next = p2;
	}
	return new_head;
}

Node* RearInsert(Node* head,int arr[],int arrSize){
	Node* rear = head;
	rear->next = NULL;
	for(int i = 0;i < arrSize;i++){
		Node* new_node = new Node(arr[i]);
		new_node->next = rear->next;
		rear->next = new_node;
		rear = new_node;
	}
	return head;
}

void Print(Node* head){
	Node* cur = head->next;
	while(cur != NULL){
		cout<<cur->data<<"  ";
		cur = cur->next;
	}
	cout<<endl;
}

int main(int argc, char const *argv[])
{
	
	int arr1[5] = {1,2,3,4,5};
	int arr2[3] = {0,3,8};
	Node* head1 = new Node;
	Node* head2 = new Node;
	head1 = RearInsert(head1,arr1,5);
	head2 = RearInsert(head2,arr2,3);
	Print(head1);				// 1,2,3,4,5
	Print(head2);				// 0,3,8
	Print(MergeLinkList(head1,head2));
	
	return 0;
}